package week1.digraph;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;

import edu.princeton.cs.introcs.In;
import graph.design.GenericGraph;

public class DiGraph extends GenericGraph<String> {

	private Map<String,Boolean> visited = null;
	
	public DiGraph() {
		super();
		visited = new HashMap<String, Boolean>();
	}
	
	public DiGraph(In in){		
		this();
		String line = in.readLine();
		while(line != null){
			if(line != null && line.length() > 0){
				String[] items = line.split(" ");
				String vertex = items[0].trim();
				this.addVertex(vertex);
				
				if(items.length > 1){
					String edge = items[1].trim();
					this.addEdgeTo(vertex, edge);
				}				
			}
			line = in.readLine();
		}
	}
	/**
	 * reversal of graph
	 * @return
	 */
	public DiGraph reverse(){
		DiGraph reverseGraph = new DiGraph();
		for(String v : this.getVertices())
		{		
			Set<String> edges = this.getEdges(v);
			for(String w : edges){
				reverseGraph.addEdgeTo(w, v);
			}
		}
		return reverseGraph;
	}
	/**
	 * bfs of all Vertices.
	 * 
	 */
	
	public void bfs(){	
		for(String v : this.getVertices()){
			if(!visited.containsKey(v)){
				bfs(v);
			}
		}
	}
	/**
	 * breadth first search for the Graph
	 * 
	 * @param source = vertex from which bfs should start
	 */
	
	public void bfs(String source){
		LinkedList<String> queue = new LinkedList<String>();
		queue.offer(source);
		String vertex = source;
		while(!queue.isEmpty()){
			vertex = queue.remove();
			Set<String> edges = this.getEdges(vertex);
			
			if(edges != null){		
				for(String destEdge : edges){				
					if(!queue.contains(destEdge)){
						queue.offer(destEdge);					
					}
				}
			}
			if(!visited.containsKey(vertex)){
				visited.put(vertex,Boolean.TRUE);
				System.out.print(vertex+ " ");
			}			
			
		}
	}
	public static void main(String[] args) {		
		In in = new In(args[0]);
		DiGraph diGraph = new DiGraph(in);
		diGraph.bfs("A");
		in.close();
		System.exit(0);
	}
}
